# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class BSTIterator:

    def __init__(self, root: TreeNode):
        self.stack = []
        while root:
            self.stack.append(root)
            root = root.left

    def next(self) -> int:
        """
        @return the next smallest number
        """
        node = self.stack.pop()
        val = node.val
        node = node.right
        while node:
            self.stack.append(node)
            node = node.left
        return val

    def hasNext(self) -> bool:
        """
        @return whether we have a next smallest number
        """
        return len(self.stack) != 0


if __name__ == '__main__':
    root = TreeNode(7)
    node3 = TreeNode(3)
    node15 = TreeNode(15)
    node9 = TreeNode(9)
    node20 = TreeNode(20)
    root.left = node3
    root.right = node15
    node15.left = node9
    node15.right = node20
    iterator = BSTIterator(root);

    re =  iterator.next(); # 返回
    # 3
    print(re)
    re =  iterator.next(); # 返回
    # 7
    print(re)
    re =  iterator.hasNext(); # 返回
    # true
    print(re)
    re =  iterator.next(); # 返回
    # 9
    print(re)
    re =  iterator.hasNext(); # 返回
    # true
    print(re)
    re =  iterator.next(); # 返回
    # 15
    print(re)
    re =  iterator.hasNext(); # 返回
    # true
    print(re)
    re =  iterator.next(); # 返回
    # 20
    print(re)
    re =  iterator.hasNext(); # 返回
    print(re)
    # false

